In graph theory, the tensor product G × H of graphs G and H is a graph such that
The tensor product is also called the direct product, categorical product, cardinal product, relational product, Kronecker product, weak direct product, or conjunction. As an operation on binary relations, the tensor product was introduced by Alfred North Whitehead and Bertrand Russell in their Principia Mathematica (1912). It is also equivalent to the Kronecker product of the adjacency matrices of the graphs (Weichsel 1962).
The notation G × H is also sometimes used to represent another construction known as the Cartesian product of graphs, but more commonly refers to the tensor product. The cross symbol shows visually the two edges resulting from the tensor product of two edges.[1]
Contents |
The tensor product is the category-theoretic product in the category of graphs and graph homomorphisms. That is, there is a homomorphism from G × H to G and to H (given by projection onto each coordinate of the vertices) such that any other graph that has a homomorphism to both G and H has a homomorphism to G × H that factors through the homomorphisms to G and H.
The adjacency matrix of G × H is the tensor product of the adjacency matrices of G and H.
If a graph can be represented as a tensor product, then there may be multiple different representations (tensor products do not satisfy unique factorization) but each representation has the same number of irreducible factors. Imrich (1998) gives a polynomial time algorithm for recognizing tensor product graphs and finding a factorization of any such graph.
If either G or H is bipartite, then so is their tensor product. G × H is connected if and only if both factors are connected and at least one factor is nonbipartite (Imrich and Klavžar, Theorem 5.29). In particular the bipartite double cover of G is connected if and only if G is connected and nonbipartite.
The Hedetniemi conjecture gives a formula for the chromatic number of a tensor product.